TNotes.leetcode

Appearance

⏰0907. 子数组的最小值之和【中等】

0907. 子数组的最小值之和【中等】 ​

1. 📝 题目描述 ​

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7。

示例 1：

txt
输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

txt
输入：arr = [11,81,94,43,3]
输出：444

提示：

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4

2. 🎯 s.1 - 单调栈 ​

c
int sumSubarrayMins(int* arr, int arrSize) {
    long long MOD = 1000000007;
    int n = arrSize;
    int* left = (int*)malloc(sizeof(int) * n);
    int* right = (int*)malloc(sizeof(int) * n);
    int* stack = (int*)malloc(sizeof(int) * n);
    int top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[stack[top]] >= arr[i]) top--;
        left[i] = top >= 0 ? i - stack[top] : i + 1;
        stack[++top] = i;
    }
    top = -1;
    for (int i = n - 1; i >= 0; i--) {
        while (top >= 0 && arr[stack[top]] > arr[i]) top--;
        right[i] = top >= 0 ? stack[top] - i : n - i;
        stack[++top] = i;
    }
    long long res = 0;
    for (int i = 0; i < n; i++) res = (res + (long long)arr[i] * left[i] % MOD * right[i]) % MOD;
    free(left); free(right); free(stack);
    return (int)res;
}
js
/**
 * @param {number[]} arr
 * @return {number}
 */
var sumSubarrayMins = function (arr) {
  const MOD = 1e9 + 7
  const n = arr.length
  const left = new Array(n),
    right = new Array(n)
  const stack = []
  for (let i = 0; i < n; i++) {
    while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) stack.pop()
    left[i] = stack.length ? i - stack[stack.length - 1] : i + 1
    stack.push(i)
  }
  stack.length = 0
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && arr[stack[stack.length - 1]] > arr[i]) stack.pop()
    right[i] = stack.length ? stack[stack.length - 1] - i : n - i
    stack.push(i)
  }
  let res = 0
  for (let i = 0; i < n; i++) res = (res + arr[i] * left[i] * right[i]) % MOD
  return res
}
py
class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(arr)
        left, right = [0] * n, [0] * n
        stack = []
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]: stack.pop()
            left[i] = i - stack[-1] if stack else i + 1
            stack.append(i)
        stack.clear()
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]: stack.pop()
            right[i] = stack[-1] - i if stack else n - i
            stack.append(i)
        return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD
  • 时间复杂度：O(n)，其中 n 是数组长度
  • 空间复杂度：O(n)

算法思路：

  • 对每个元素，用单调栈求其作为最小值的左右边界范围
  • 左边界：左侧第一个严格更小的元素位置；右边界：右侧第一个 ≤ 的位置
  • 每个元素的贡献 = arr[i] * left[i] * right[i]